Search for: All records

Abstract Let$$f$$ $f$be an analytic polynomial of degree at most$$K-1$$ $K-1$. A classical inequality of Bernstein compares the supremum norm of$$f$$ $f$over the unit circle to its supremum norm over the sampling set of the$$K$$ $K$-th roots of unity. Many extensions of this inequality exist, often understood under the umbrella of Marcinkiewicz–Zygmund-type inequalities for$$L^{p},1\le p\leq \infty $$ $L^p,1\le p\le \infty$norms. We study dimension-free extensions of these discretization inequalities in the high-dimension regime, where existing results construct sampling sets with cardinality growing with the total degree of the polynomial. In this work we show that dimension-free discretizations are possible with sampling sets whose cardinality is independent of$$\deg (f)$$ $deg\left(f\right)$and is instead governed by the maximumindividualdegree of$$f$$ $f$;i.e., the largest degree of$$f$$ $f$when viewed as a univariate polynomial in any coordinate. For example, we find that for$$n$$ $n$-variate analytic polynomials$$f$$ $f$of degree at most$$d$$ $d$and individual degree at most$$K-1$$ $K-1$,$$\|f\|_{L^{\infty }(\mathbf{D}^{n})}\leq C(X)^{d}\|f\|_{L^{\infty }(X^{n})}$$ ${\parallel f\parallel }_{L^{\infty }\left(D^n\right)}\le C{\left(X\right)}^d{\parallel f\parallel }_{L^{\infty }\left(X^n\right)}$for any fixed$$X$$ $X$in the unit disc$$\mathbf{D}$$ $D$with$$|X|=K$$ $\left|X\right|=K$. The dependence on$$d$$ $d$in the constant is tight for such small sampling sets, which arise naturally for example when studying polynomials of bounded degree coming from functions on products of cyclic groups. As an application we obtain a proof of the cyclic group Bohnenblust–Hille inequality with an explicit constant$$\mathcal{O}(\log K)^{2d}$$ $O{(logK)}^{2d}$. 

Recent efforts in Analysis of Boolean Functions aim to extend core results to new spaces, including to the slice binom([n],k), the hypergrid [K]ⁿ, and noncommutative spaces (matrix algebras). We present here a new way to relate functions on the hypergrid (or products of cyclic groups) to their harmonic extensions over the polytorus. We show the supremum of a function f over products of the cyclic group {exp(2π i k/K)}_{k = 1}^K controls the supremum of f over the entire polytorus ({z ∈ ℂ:|z| = 1}ⁿ), with multiplicative constant C depending on K and deg(f) only. This Remez-type inequality appears to be the first such estimate that is dimension-free (i.e., C does not depend on n). This dimension-free Remez-type inequality removes the main technical barrier to giving 𝒪(log n) sample complexity, polytime algorithms for learning low-degree polynomials on the hypergrid and low-degree observables on level-K qudit systems. In particular, our dimension-free Remez inequality implies new Bohnenblust-Hille-type estimates which are central to the learning algorithms and appear unobtainable via standard techniques. Thus we extend to new spaces a recent line of work [Eskenazis and Ivanisvili, 2022; Huang et al., 2022; Volberg and Zhang, 2023] that gave similarly efficient methods for learning low-degree polynomials on the hypercube and observables on qubits. An additional product of these efforts is a new class of distributions over which arbitrary quantum observables are well-approximated by their low-degree truncations - a phenomenon that greatly extends the reach of low-degree learning in quantum science [Huang et al., 2022].